One real world analogy is the methods for constructing roadway networks that allow drivers to get from a starting location to a destination while satisfying real world constraints such as 1) a ceiling on the amount of tax people are willing to pay to fund roadway construction; 2) a desire to maximize speed of travel subject to safety constraints; and 3) a desire to avoid traffic jams at peak travel times of day.
In this analogy, the cars are similar to the data sent over a computer network and the starting locations and destinations represent the host computers connected to the network. The constraints translate directly into cost, speed and congestion constraints in computer networks.
The basic quality of solving these types of problems is that they get much harder to solve efficiently as the number of starting locations and destinations (e.g., host computers) increases. As a starting point, consider how three destinations can be connected together. FIGS. 1A and 1B show that there are really only two alternatives. The number of ways to connect the destinations together grows along with the number of destinations, for example, with four destinations, some of the possible methods of connection are shown in FIGS. 1C, 1D, 1E and 1F.
As can be seen from the figures, both the number of connections between nodes and the number of different ways of making those connections grows faster than the number of connections. For example, a set of 6 nodes can have more than twice as many alternative ways to connect the nodes as a set of 3 nodes. Also, the possible number of connections between the nodes can vary from, on the low side, the number of nodes (N) minus 1 for destinations connected, for example, along a single line as shown in FIG. 1C, to N(N−1)/2 connections as shown in FIG. 1F, where every single node has a direct connection to every other node.
Another measure of the performance of a network is the diameter of the network, which refers to how many connections need to be traveled in order to get from any one destination to another. In the network shown in FIG. 1C, its economy in the number of connections (3) is offset by the consequence that the only path, from one end of the network to the other, requires travel across three connections, thus slowing the journey. On the other hand as shown in FIG. 1F, the large number of connections results in every destination only being one connection away from any other, permitting more rapid travel.
The two networks shown in FIGS. 1C and 1F can also have very different behavior at peak traffic times. Assuming that each connection can support the same rate of traffic flow, the two end point nodes of the network shown in FIG. 1C will be affected if there is a lot of traffic traveling between the two nodes in the middle of the line. Conversely, in network shown in FIG. 1F, since there is an individual connection between every possible combination of nodes, traffic flowing between two nodes is not affected at all by traffic flowing between a different pair of nodes.
Another difficulty arises in the construction of computer networks: It is difficult to have a large number of connections converging on a single point, such as shown in FIG. 1F. In a computer data center, the devices that allow multiple connections to converge are called switches. These switches that allow multiple connections to converge typically have physical limitations on the number of connections or ports, for example, around 50 ports for inexpensive switches, and can approach 500 ports for more modem, expensive switches. This means that for a fully-meshed network like that shown in FIG. 1F where delays and congestion are minimized, no more than, for example, 499 destination hosts could be connected together.